package club.babyf.nativeai.demo.algorithm;

/**
 * _21_ReverseKGroupList.
 *
 * @author zhanglei.
 * @date 2025/7/20 19:17.
 * @description 在一个链表中，每k个元素链表进行翻转.
 */
public class _21_ReverseKGroupList {

    public ListNode reverseKGroupList(ListNode head, int k) {
        if (head == null || k <= 1) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode start = head;

        while (start != null) {
            ListNode end = pre;
            for (int i = 0; i < k; i++) {
                if (end.next == null) {
                    return dummy.next;
                }
                end = end.next;
            }

            ListNode nextGroup = end.next;
            end.next = null;
            pre.next = reverse(start);
            start.next = nextGroup;

            pre = start;
            start = nextGroup;
        }

        return dummy.next;
    }

    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }

    public static class ListNode {

        int value;

        ListNode next;

        public ListNode(int value) {
            this.value = value;
        }

        public ListNode(int value, ListNode next) {
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            ListNode current = this;
            while (current != null) {
                sb.append(current.value);
                ListNode next = current.next;
                if (next != null) {
                    sb.append(" -> ");
                }
                current = next;
            }
            return sb.toString();
        }

    }

    public static void main(String[] args) {
        _21_ReverseKGroupList reverseKGroupList = new _21_ReverseKGroupList();
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        System.out.println(head);
        ListNode listNode = reverseKGroupList.reverseKGroupList(head, 2);
        System.out.println(listNode);
    }

}
